class Solution {
    public int rob(int[] nums) {
        if (nums.length == 1) {
            return nums[0];
        }
        // 偷了第一件屋子，就不能偷最后一间
        int ans1 = judge(nums, 0, nums.length - 2);
        // 偷了最后一间，就不能偷第一间
        int ans2 = judge(nums, 1, nums.length - 1);
        return Math.max(ans1, ans2);
    }

    public int judge(int[] nums, int start, int end) {
        int[] d = new int[nums.length];
        for (int i = start; i <= end; i++) {
            int v1 = (i >= 1) ? d[i - 1] : 0;
            int v2 = (i >= 2) ? d[i - 2] : 0;
            d[i] = Math.max(v1, v2 + nums[i]);
        }
        return d[end];
    }
}